Most computer programs are organized around one of two models: thread-oriented or data-oriented. In the thread-oriented model, the programmer organizes a program into a number of parallel activities, each a sequential program or “thread” of its own. One or more computer processors will execute each of these threads. Although a single processor may be capable of executing multiple tasks in quasi-parallel fashion by switching rapidly between the tasks, in general, only one thread executes on any one physical processor at a given time. Other threads will be either ready, but waiting for a processor to become available, or blocked waiting for some event, such as the completion of an I/O operation or the availability of some resource. When a thread is not executing on a processor, its state (e.g. the contents of various registers) is preserved in a block of memory. The software typically used to move threads between these three states, and to maximize overall system performance is known as a scheduler. In many systems, the scheduler is part of the core operating system.
In the data-oriented model, the programmer organizes a program around the input/output operations and the internal flow of data among sections of a program known as “compute blocks.” The input data might originate from a human user, a storage device, another program, or another computer via a communication link. When input data becomes available, it is organized into a logical grouping, which will be referred to herein as a “work item.” The work item is queued, waiting for the first compute block to process it. Once processed by the first compute block, the work item is either enqueued waiting for a second compute block to process it or is completed.
In most computer systems, threads and work items are managed by different schedulers. Furthermore, in those systems in which both threads and work items are used, threads waiting to be processed are stored in queues that are separate from those in which work items are stored.